W1054 永无止境的反转

Dec 16, 2024 11:44 AM

Mar 07, 2025 9:50 AM

1 Description

给定一条长度为 $n$ 的数轴，初始 $n$ 个整点全为白色。接下来将执行若干次反转操作：将某个区间内的所有白色整点变为黑色，所有黑色整点变为白色。

举例来说，若数轴为 $W B W W B B B B$ ，将其中红色部分反转后变为 $W W B B W B B B$ 。其中 $W$ 和 $B$ 分别表示白色和黑色。

你的任务是在每次操作后，求出当前还有多少白色块。注意，每次操作将会永久地改变数轴。

2 Input

\begin{aligned} n & m \\ l_{1} & r_{1} \\ l_{2} & r_{2} \\ ⋮ \\ l_{m} & r_{m} ​ \end{aligned}

其中 $n$ 表示数轴的长度，而 $m$ 表示操作数。

接下来 $m$ 行，每行两个数表示当前反转了 $[l, r]$ 区间内的元素。

2.1 数据范围

$n, m, l_{i} , r_{i} $ 为整数。
$1 \leq l_{i} \leq r_{i} \leq n \leq 10^{18}$ 。
$1 \leq m \leq 2 \times 10^{3}$ 。

3 Output

\begin{aligned} w_{1} \\ w_{2} \\ ⋮ \\ w_{m} ​ \end{aligned}

表示每次操作后，当前数轴上有多少白点。

4 示例

Sample Input 1

Sample Output 1

3
6
4

5 Hint

操作序列：

$1 2 3 4 5 6 7 8 9 0$
$W W W W W W W W W W \to B B B B B B B W W W \to 3$
$B B B B B B B W W W \to B B W W W W W B B W \to 6$
$B B W W W W W B B W \to B B W W B B B W W B \to 4$

Solution

详情：关于本题的回答

线段树+离散化

$O (m \log m)$

其实离散化+线段树就可以解决了！ 将 $m$ 个点离散化(其实这里 $m$ 也可以取到 $10^{5}$ 数量级)，然后就是正常的区间操作了

#include<bits/stdc++.h>
#define int long long
using namespace std;
#define lc root<<1
#define rc root<<1|1

struct Node {
    int l, r;
    int len;
    int white;
    bool flip;
};

const int MAX_NODES = 4 * 400000; // 足够大的节点数，防止越界
Node tree[MAX_NODES];
vector<int> p;

void build(int root, int l, int r) {
    int len = p[l + 1] - p[l];
    tree[root] = {l,r,len,len,false};
    if (l == r) {
        return;
    }
    int mid = (l + r) / 2;
    build(lc, l, mid);
    build(rc, mid + 1, r);
    tree[root].len = tree[lc].len + tree[rc].len;
    tree[root].white = tree[lc].white + tree[rc].white;
}

void push(int root) {
    if (tree[root].flip && tree[root].l != tree[root].r) {
        for (int child : {lc, rc}) {
            tree[child].flip = !tree[child].flip;
            tree[child].white = tree[child].len - tree[child].white;
        }
        tree[root].flip = false;
    }
}

void update(int root, int l, int r) {
    if (tree[root].r < l || tree[root].l > r) {
        return;
    }
    if (l <= tree[root].l && tree[root].r <= r) {
        tree[root].flip = !tree[root].flip;
        tree[root].white = tree[root].len - tree[root].white;
        return;
    }
    push(root);
    update(lc, l, r);
    update(rc, l, r);
    tree[root].white = tree[lc].white + tree[rc].white;
}

signed main() {
    ios::sync_with_stdio(false);cin.tie(0);

    int n, m;
    cin >> n >> m;

    p.push_back(1);
    p.push_back(n + 1);

    vector<pair<int, int>> ops;
    for (int i = 0; i < m; ++i) {
        int l, r;
        cin >> l >> r;
        ops.emplace_back(l, r);
        p.push_back(l);
        p.push_back(r + 1);
    }

    sort(p.begin(), p.end());
    auto last = unique(p.begin(), p.end());
    p.erase(last, p.end());

    int siz = p.size() - 1;
    if (siz == 0) {
        for (int i = 0; i < m; ++i) {
            cout << "0\n";
        }
        return 0;
    }

    build(1, 0, siz - 1);

    for (auto& op : ops) {
        int l = op.first;
        int r = op.second;

        int i = lower_bound(p.begin(), p.end(), l) - p.begin();
        int j = lower_bound(p.begin(), p.end(), r + 1) - p.begin();

        if (i < j) {
            update(1, i, j - 1);
        }
        cout << tree[1].white << '\n';
    }

    return 0;
}

区间分段管理

$O (m^{2})$

如果区间存在重叠，则将区间分为三个部分，否则保留原区间

代码：

By Gemini 2.0 Flash Thinking Experimental 01-21

#include <iostream>
#include <vector>
#include <map>

using namespace std;

int main() {
    long long n; // 数轴长度
    int m;       // 操作次数
    cin >> n >> m;

    map<long long, bool> seg; // 区间颜色，key: 区间起点, value: true=白色, false=黑色
    seg[1] = true;            // 初始整个区间 [1, n] 为白色

    for (int i = 0; i < m; ++i) {
        long long l, r; // 操作区间 [l, r]
        cin >> l >> r;

        map<long long, bool> nseg; // 操作后的新区间颜色

        for (auto const& [st, color] : seg) { // 遍历当前所有区间
            long long cur_st = st;    // 当前区间起点
            long long cur_ed;        // 当前区间终点

            auto it = seg.upper_bound(st);  // 找到下一个区间的起点
            if (it == seg.end()) {
                cur_ed = n; // 如果没有下一个区间，则当前区间延伸到数轴末尾
            } else {
                cur_ed = it->first - 1; // 否则，当前区间终点是下一个区间的起点 - 1
            }

            long long ol_st = max(cur_st, l); // 重叠区间起点
            long long ol_ed = min(cur_ed, r); // 重叠区间终点

            if (ol_st <= ol_ed) { // 如果有重叠
                if (cur_st < ol_st) {       // 当前区间在重叠区间之前的部分
                    nseg[cur_st] = color;  // 颜色不变
                }
                nseg[ol_st] = !color;      // 重叠区间颜色反转
                if (ol_ed < cur_ed) {       // 当前区间在重叠区间之后的部分
                    nseg[ol_ed + 1] = color; // 颜色不变
                }
            } else { // 如果没有重叠
                nseg[cur_st] = color; // 整个区间颜色不变
            }
        }
        seg = nseg; // 更新区间颜色

        long long cnt = 0; // 白色块数量
        for (auto const& [st, color] : seg) {
            if (color) {  // 如果是白色区间
                long long cur_st = st;
                long long cur_ed;
                auto it = seg.upper_bound(st);
                if (it == seg.end()) {
                    cur_ed = n;
                } else {
                    cur_ed = it->first - 1;
                }
                cnt += (cur_ed - cur_st + 1); // 累加白色块长度
            }
        }
        cout << cnt << '\n'; // 输出白色块数量
    }

    return 0;
}